//给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。 
//
// 说明: 叶子节点是指没有子节点的节点。 
//
// 示例: 
//给定如下二叉树，以及目标和 sum = 22， 
//
//               5
//             / \
//            4   8
//           /   / \
//          11  13  4
//         /  \    / \
//        7    2  5   1
// 
//
// 返回: 
//
// [
//   [5,4,11,2],
//   [5,8,4,5]
//]
// 
// Related Topics 树 深度优先搜索

package leetcode.editor.cn;
//leetcode submit region begin(Prohibit modification and deletion)

import leetcode.editor.cn.model.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
class P113PathSumIi {
	private List<List<Integer>> res = new ArrayList<>();

	public List<List<Integer>> pathSum(TreeNode root, int sum) {
		if (root == null) {
			return res;
		}
		dfs(root, sum, new LinkedList<Integer>());
		return res;
	}

	private void dfs(TreeNode root, int sum, LinkedList<Integer> tmp) {
		if (root == null) return;
		tmp.add(root.val);
		if (root.val == sum && root.left == null && root.right == null) {
			res.add(new ArrayList<Integer>(tmp));
		}
		dfs(root.left, sum - root.val, tmp);
		dfs(root.right, sum - root.val, tmp);
		tmp.removeLast();
	}
}
//leetcode submit region end(Prohibit modification and deletion)
